package mazeAssignment;

/**
 * An implementation of a binary-node for the BinaryTree class.
 * @author Marcel Hekman
 */
class BinaryNode<AnyType extends Comparable<? super AnyType>> {
	
	public AnyType element;
	public BinaryNode<AnyType> left;
	public BinaryNode<AnyType> right;
	
	private int height;
	private int size;
	
	
	public BinaryNode()
	{
		this(null);
	}
	
	public BinaryNode(AnyType e)
	{
		this(e, null, null);
	}
	
	public BinaryNode(AnyType e, BinaryNode<AnyType> l, BinaryNode<AnyType> r)
	{
		this.element = e;
		this.left = l;
		this.right = r;
		
		this.height = 0;
		this.size = 1;
		
		if(this.left != null)
		{
			this.height = this.left.height();
			this.size += this.left.size;
		}
		
		if(this.right != null)
		{
			this.height = Math.max(this.height, this.right.height());
			this.size += this.right.size;
		}
		
		this.height++;
	}
	
	
	
	
	public void add(AnyType item)
	{
		int compValue = item.compareTo(this.element);
		
		if(compValue < 0)
		{
			if(this.left != null)
				this.left.add(item);
			else
				this.left = new BinaryNode<AnyType>(item);
		}
		else if(compValue > 0)
		{
			if(this.right != null)
				this.right.add(item);
			else
				this.right = new BinaryNode<AnyType>(item);
		}
		else
		{
			throw new IllegalArgumentException("Duplicate!");
		}
		
		this.size++;
		this.height = Math.max( this.leftHeight(), this.rightHeight() ) + 1; 
	}
	
	
	
	
	/**
     * O(log N)
     * @returns Het item op positie 'k'
     * @throws IllegalArgumentException als 'k' ongeldig is.
     */
    public BinaryNode<AnyType> findKth(int k)
    {
        if(k < 1 || k > size)
            throw new IllegalArgumentException("BinaryNode.findKth()");
        
        int leftSize = this.leftSize();
        
        //In linker tree
        if(k <= leftSize)
        {
            return this.left.findKth(k);
        }
        //In rechter tree
        else if(k > leftSize + 1)
        {
            return this.right.findKth(k - leftSize - 1);
        }
        //Het huidige item
        else
        {
            return this;
        }
    }
    
    protected AnyType findMin()
    {
       BinaryNode<AnyType> current = this;
       
       while(current.left != null)
    	   current = current.left;
       
       return current.element;
    }   
   
    
    protected AnyType findMax()
    {
    	BinaryNode<AnyType> current = this;
        
        while(current.right != null)
     	   current = current.right;
        
        return current.element;
    }
    
    
    /**
     * Verwijdert het opgegeven item
     */
    public BinaryNode<AnyType> remove(AnyType item)
    {
    	int compValue = this.element.compareTo(item);
    	
    	//Naar links
    	if(compValue > 0 && this.left != null)
    	{
    		this.left = this.left.remove(item);
    	}
    	//Naar rechts
    	else if(compValue < 0 && this.right != null)
    	{
    		this.right = this.right.remove(item);
    	}
    	else
        {
    		//Remove from left subtree
    		if(leftSize() > rightSize())
    		{
    			this.element = this.left.findMax();
    			this.left = this.left.removeMax();
    		}
    		//Remove from right subtree
    		else if(this.right != null)
	        {
	        	this.element = this.right.findMin();
	        	this.right = this.right.removeMin();
	        }
    		//No subtrees
	        else
	        {
	        	return null;
	        }
        }
        
        this.size--;
        return this;
    }
    
   
    /**
     * Verwijdert het eerste item in de subtree
     * O(log N)
     */
    protected BinaryNode<AnyType> removeMin()
    {
    	BinaryNode<AnyType> current = this;
    	
    	//This is the minimum item
    	if(current.left == null)
    		return current.right;
    	
    	
    	while(current.left.left != null)
    	{
    		current.size--;
    		current = current.left;
    	}
    	
    	current.size--;
    	current.left = current.left.right;
    	
    	return this;
    	
    	/*
    	while(current.left != null)
        //De te verwijderen node is nog te ver weg dus een recursieve aanroep
        if(left != null && left.left != null)
        {
        	this.size--;
        	return left.removeMin();
        }
        //De node in this.left verwijderen
        else if(left != null)
        {
        	AnyType returnValue = this.left.element;
        	this.size--;
            this.left = this.left.right;
            return returnValue;
        }
        
        this.size--;
        return this;
        */
    }
    
    /**
     * Verwijdert het laatste item in de subtree
     * O(log N)
     */
    protected BinaryNode<AnyType> removeMax()
    {
    	BinaryNode<AnyType> current = this;
    	
    	//This is the maximum item
    	if(current.right == null)
    		return current.left;
    	
    	
    	while(current.right.right != null)
    	{
    		current.size--;
    		current = current.right;
    	}
    	
    	current.size--;
    	current.right = current.right.left;
    	
    	return this;
    	/*
        //De te verwijderen node is nog te ver weg dus een recursieve aanroep
        if(right != null && right.right != null)
        {
        	this.size--;
            return right.removeMax();
        }
        //De node in this.right verwijderen
        else if(right != null)
        {
        	AnyType returnValue = this.right.element;
        	this.size--;
            this.right = this.right.left;
            return returnValue;
        }
        //De huidige node moet verwijdert worden
        else
        {
            throw new UnsupportedOperationException("BinaryNode.removeMax()");
        }
        */
    }
	
    
    public int size()
    {
        return size;
    }
    public int leftSize()
    {
        if(this.left == null)
            return 0;
        
        return this.left.size();
    }
    public int rightSize()
    {
        if(this.right == null)
            return 0;
        
        return this.right.size();
    }
    
    
	public int height()
	{
		return this.height;
	}
	public int leftHeight()
    {
        if(this.left == null)
            return 0;
        
        return this.left.height();
    }
    public int rightHeight()
    {
        if(this.right == null)
            return 0;
        
        return this.right.height();
    }
	
    
	public void printInOrder()
	{
		if(this.left != null)
			this.left.printInOrder();
		
		System.out.println(element.toString());
		
		if(this.right != null)
			this.right.printInOrder();
	}
}
